package acwing.堆;

import java.io.BufferedInputStream;
import java.util.Scanner;

/**
 * @description:
 * @author: qian
 * @createDate: 2021/11/17
 */
public class 模拟堆 {

    static int N = 100010;
    //ph得到下标,hp得到对应插入的目前个数
    static int[] h = new int [N], hp = new int[N], ph = new int[N];

    static int size = 0;

    public static void down(int u) {

        int t = u;
        if (u * 2 <= size && h[u * 2] < h[t]) t = t * 2;
        if(u * 2 + 1 <= size && h[u*2+1]< h[t]) t = u*2+1;
        if (u != t) {
            heapSwap(u, t);
            down(t);
        }
    }
    public static void up(int u) {
        while (u / 2 != 0 && h[u / 2] > h[u]) {
            heapSwap(u / 2, u);
            u /= 2;
        }
    }

    private static void heapSwap(int a, int b) {

        int temp = h[a];
        h[a] = h[b];
        h[b] = temp;

        temp = ph[hp[a]];
        ph[hp[a]] = ph[hp[b]];
        ph[hp[b]] = temp;
        temp = hp[a];
        hp[a] = hp[b];
        hp[b] =temp;
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(new BufferedInputStream(System.in));
        //m表示目前插了几个节点
        int n = in.nextInt(),m=0;

        while (n-- != 0) {
            String s = in.next();
            if (s.equals("I")) {
                int a = in.nextInt();
                h[++size] = a;
                m++;
                //更新两个映射数组
                ph[m]=size;hp[size]=m;
                up(size);
            }
            else if(s.equals("PM")){
                System.out.println(h[1]);
            }
            else if(s.equals("DM")){
                heapSwap(1,size);
                size--;
                down(1);
            }
            else if(s.equals("D")){
                int k = in.nextInt();
                k = ph[k];
                heapSwap(size,k);
                size--;
                //这里是down和up，如果删除最后一层元素，那么可能下移或者上移，否则下移
                down(k);up(k);
            }
            else {
                int k = in.nextInt(),x = in.nextInt();
                k = ph[k];
                h[k] = x;
                //修改，可能改大或者改小
                down(k);up(k);
            }
        }
    }
}
